package com.example.demo.arithmetic.algorithm.dynamic_programing;

import com.example.demo.arithmetic.algorithm.greedy.bag.BagProblem;

import java.util.Arrays;

/**
 * 完全背包问题
 * 物品不限量 可以拿重复的物品
 */
/*
   背包容量:
   0    1   2   3   4   5    6
1  0    0   c   c   cc  cc   ccc     青铜
2  0    0   c   s   cc  sc   ccc     白银
3  0    0   c   s   a   a/sc ac       黄金
:物品编号
if(放得下){                         i表示还可以拿同等物品
    dp[i][j] = Math.max(dp[i-1][j],dp[i][j-item.weight]+item.sum)
}else{
    dp[i][j]=dp[i-1][j]
}
 */
public class KnapsackProblemComplete {
    public static void main(String[] args) {
        BagProblem.Item[] items = new BagProblem.Item[]{
                new BagProblem.Item(1, 2, 3),// 青铜c
                new BagProblem.Item(2, 3, 4),// 白银s
                new BagProblem.Item(3, 4, 7),// 黄金a
        };

        //        System.out.println(new KnapsackProblemComplete().dpSelect(items, 6));
        System.out.println(new KnapsackProblemComplete().dpSelect2(items, 6));
    }

    /**
     * 降维
     *
     * @param items
     * @param n
     * @return
     */
    private int dpSelect2(BagProblem.Item[] items, int n) {
        int[] dp = new int[n + 1];
        // 特殊处理第一行 移动到下面
        //        for (int j = 0; j < n+1; j++) {
        //            if (j >= item0.weight) {
        //                dp[j] = dp[j - item0.weight] + item0.sum;
        //            }
        //        }
        // 特殊处理其余行 i=1开始
        for (int i = 0; i < items.length; i++) {
            BagProblem.Item item = items[i];
            for (int j = 0; j < n + 1; j++) {
                if (j >= item.weight) {
                    dp[j] = Math.max(dp[j], dp[j - item.weight] + item.sum);
                }
            }
            System.out.println(Arrays.toString(dp));
        }
        return dp[n];
    }

    private int dpSelect(BagProblem.Item[] items, int n) {
        int[][] dp = new int[items.length][n + 1];
        BagProblem.Item item0 = items[0];
        // 特殊处理第一行
        for (int j = 0; j < dp[0].length; j++) {
            if (j < item0.weight) {
                dp[0][j] = 0;
            } else {
                dp[0][j] = dp[0][j - item0.weight] + item0.sum;
            }
        }
        // 特殊处理其余行 i=1开始
        for (int i = 1; i < dp.length; i++) {
            BagProblem.Item item = items[i];
            for (int j = 0; j < dp[0].length; j++) {
                if (j < item.weight) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - item.weight] + item.sum);
                }
            }
            printDp(dp);
        }
        return dp[dp.length - 1][n];
    }

    private void printDp(int[][] arr) {
        for (int[] its : arr) {
            for (int anInt : its) {
                System.out.print(anInt + " ");
            }
            System.out.println();
        }
    }
}

